# Definition for singly-linked list.

import heapq
from typing import List

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
    def __lt__(self, value):
        return self.val < value.val

# 因为改了 ListNode 的定义，没法在 leetcode 里跑…
class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        heapq.heapify(lists)

        head, tail = None, None
        while len(lists) > 0:
            minNode = heapq.heappop(lists)
            if head == None:
                head = minNode
                tail = minNode
            else:
                tail.next = minNode
                tail = tail.next
            nnext = minNode.next
            if nnext != None:
                heapq.heappush(lists, nnext)
        return head